The linear complementarity problem is a continuous optimization problem thatgeneralizes convex quadratic programming, Nash equilibria of bimatrix games andseveral such problems. This paper presents a continuous optimizationformulation for the weighted independence number of a graph by characterizingit as the maximum weighted $\ell_1$ norm over the solution set of a linearcomplementarity problem (LCP). The minimum $\ell_1$ norm of solutions of thisLCP is a lower bound on the independent domination number of the graph. Unlikethe case of the maximum $\ell_1$ norm, this lower bound is in general weak, butwe show it to be tight if the graph is a forest. Using methods from the theoryof LCPs, we obtain a few graph theoretic results. In particular, we provide astronger variant of the Lov\'{a}sz theta of a graph. We then provide sufficientconditions for a graph to be well-covered, i.e., for all maximal independentsets to also be maximum. This condition is also shown to be necessary forwell-coveredness if the graph is a forest. Finally, the reduction of themaximum independent set problem to a linear program with (linear)complementarity constraints (LPCC) shows that LPCCs are hard to approximate.
展开▼
